package 线.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 * @author ycc
 * @date 2025/6/29
 * 1
 *  \
 *   2
 *  /
 *  3
 */
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

//        preOrder(root);
//        System.out.println("******");

//        inOrder(root);
//        System.out.println("******");

//        postOrder(root);
//        System.out.println("******");
//
//        levelOrder2(root);
//        preOrder(root);
//        System.out.println("******");
        flip2(root);
        preOrder3(root);
    }

    /**
     * 二叉树翻转 非递归
     * @param root
     * @return
     */
    public static TreeNode flip2(TreeNode root) {
        if(root == null) {
            return null;
        }
        // 双端队列，先进先出，但是可以反转，先进后出， 代替栈的功能。
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while(!deque.isEmpty()) {
            TreeNode node = deque.pop();
//            System.out.println(node.val);
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if(node.right != null) {
                deque.push(node.right);
            }
            if(node.left != null) {
                deque.push(node.left);
            }
//            TreeNode temp = node.left;
//            node.left = node.right;
//            node.right = temp;
        }
        return root;
    }

    /**
     * 翻转二叉树
     * @param root
     * @return
     */
    public static TreeNode flip(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode left = flip(root.left);
        TreeNode right = flip(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public static void preOrder3(TreeNode root) {
        if(root == null) {
            return;
        }
        // 双端队列，先进先出，但是可以反转，先进后出， 代替栈的功能。
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while(!deque.isEmpty()) {
            TreeNode node = deque.pop();
            System.out.println(node.val);
            if(node.right != null) {
                deque.push(node.right);
            }
            if(node.left != null) {
                deque.push(node.left);
            }
        }
    }

    public static void preOrder2(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 前序遍历
     * @param root
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 中序遍历
     * @param root
     */
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

    /**
     * 中序遍历
     * @param root
     */
    public static void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }

    public static void levelOrder2(TreeNode root) {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            System.out.println(temp.val);
            if(temp.left != null) {
                queue.offer(temp.left);
            }
            if(temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }

    /**
     * 层序遍历
     * @param root
     */
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}
